This invention relates generally to processing data traffic and more particularly a technique for providing quality of service (QoS) for individual Internet Protocol (IP) data flows transferred via a router or other such suitable switch. The present invention describes a state dependent dynamic triggering scheme (SDDTS) for flow based QoS shortcuts.
The Internet has grown rapidly in the last several years. In order to support increasing demands for real-time and multimedia applications as well as mission critical applications, Internet Protocol (IP) need to support quality of service (QoS). QoS is a networking term that specifies a level of service based on, for example, throughput, delay, jitter and/or loss through a network. In general, QoS approaches can be divided into two main categories: flow-based and class-based. Flow-based QoS is designed to provide QoS assurance for each individual IP flow. IP specifies the format of data packets or datagrams and the addressing scheme to route the data packets or data grams to the desired destination in a network. An IP flow is defined as a set of packets matching a particular profile. A profile can be defined, for example, in terms of source/destination IP addresses, IP protocol, source/destination port numbers, and Type of Service (ToS) requirements. A typical example of flow based QoS is the Integrated Service model proposed by the Intserv working group of the Internet Engineering Taskforce (IETF). The QoS Integrated Service model is further discussed by J. Wroclawski in: xe2x80x9cSpecification of the Controlled-Load Network Element Service,xe2x80x9d in IETF RFC2211, September, 1997, incorporated herein by reference. S. Shenker, C. Partridge, and R. Guerin discuss another example of QoS in: xe2x80x9cSpecification of Guaranteed Quality of Service,xe2x80x9d in IETF RFC2212, September, 1997, incorporated herein by reference. The Integrated Service model provides fine granularity and flexibility in specifying flows. However, the service model requires storing states on a per-flow basis at each network node and an end-to-end signaling protocol such as Resource ReServation Protocol (RSVP). Using RSVP, an application must reserve resources along a route from source to destination. This procedure is problematic in that the reserved resources may be unavailable for additional processing needs and may result in decreased throughput. Further, RSVP raises concerns regarding the scalability of the approach due to the fact that the number of active flows can be quite large. In order to avoid the scalability problem with flow-based QoS, class-based QoS, which is also referred as Class of Service (CoS), is proposed to provide differentiated service for each class. For example, the Differentiated Service model is proposed by the Diffserv working group of IETF. The Differential Service Model is discussed by S. Blake, D. Black, M. Carlson, E. Davies, Z. Wang and W. Weiss in: xe2x80x9cAn Architecture for Differentiated Services,xe2x80x9d in IETF RFC2475, December, 1998, incorporated herein by reference. Generally, in a class-based QoS model, packets are marked as different classes and get served accordingly. Although class-based QoS may be more scalable, but it does not have the fine granularity of the flow-based approach. Thus there exists no assurance in class-based QoS for each individual flow within a class.
Since each approach has its own pros and cons, a network may need both models in order to provide adequate service for different types of applications. For example, class-based QoS may be enough for the majority of the Internet traffic that may not need fine granularity of service levels or require QoS assurance on a per-flow basis. Class-based QoS can be realized by preferential treatment for different classes of data traffic at each router in the network or by mapping different classes of data traffic onto different label switching paths (LSPs). LSPs may include, for example, Cisco Corporation""s Tag switching paths, Multipoint-to-Point Tree (MPTs) IP switching paths in Ascend Corporation""s IP Navigator and LSPs in MPLS (Multiprotocol Label Switching).
On the other hand, some mission critical applications may require tight control on packet loss and delay on each individual flow. In addition, some voice or video traffic may require minimum jitter which may cause degradation of the data signal for each individual flow. Class-based QoS may not be suitable for such applications, and thus flow-based QoS may be necessary for those types of applications. Flow-based QoS can be achieved by using explicit routes in MPLS, or with NHRP (Next Hop Resolution Protocol) shortcuts as proposed in MPOA (Multiprotocol Over ATM with Asynchronous Transfer Mode (ATM) underneath IP. MPOA enables ATM services to be integrated with existing local area networks (LANs) that use Ethernet, token ring or TCP/IP protocols. IP switching, as one of the key advances in IP technology, is designed to improve the performance and scalability of IP as well as providing QoS. Two of the main IP switching products, IP switch by Nokia, Corp. and Cell Switch Router by Toshiba, Corp., use flow-based shortcuts for long-lived flows and hop-by-hop routing for the rest of the traffic. A shortcut may be defined as a directed forwarding path associated with some label, for example, link layer address, such that data packets are efficiently routed without requiring the need for an IP routing table lookup at each hop.
In all those flow-based shortcut approaches, there is certain overhead associated with each shortcut setup. Since existing routers have limited resources in processing power and memory space, there are upper bounds on shortcut setup rates and number of simultaneous shortcut connections. Hence, it is important to investigate how to, most efficiently, trigger shortcut setup and tear down where the above physical limits are taken into account.
In previous work, researchers have studied the effect of the two triggering parameters, for example, onset trigger and abatement period, on the resource usage measured by average shortcut setup rate and average number of simultaneous shortcuts. Studies have concluded that a larger onset trigger may reduce both shortcut setup rate and number of simultaneous shortcuts, however, at the expense of forcing more packets to follow the default path. Further studies have indicated, that a larger abatement period may increase the number of simultaneous shortcuts, but decreases the shortcut setup rate.
Work in this area is limited. In particular, most of the prior art systems have focused on evaluating the performance of some static schemes. Generally, researchers have studied a static scheme where two parameters, the onset trigger and the timeout or some variations thereof, are used. Onset trigger may be defined as the number of packets that must be received, from the same flow, before triggering a shortcut to be setup. Timeout, also referred as the abatement period, is the preset idle time period before shortcut tearing down is triggered. The parameter setting is statically assigned based on some predefined IP traffic statistics. However, the static scheme does not take into account, for example, system resource limitations and/or the variability of network data traffic characteristics. To solve this problem an xe2x80x9cAdaptive Resource Management for Flow-Based IP/ATM Hybrid Switching Systems,xe2x80x9d in IEEE INFOCOM, March 1998, by H. Che and S. Li, incorporated herein by reference, illustrates an adaptive flow identification/classification scheme for resource balancing in flow-based IP switching. The objective of the adaptive flow identification/classification scheme is to minimize the relative differences of utilization among the following three constrained resources: hop-by-hop routing, shortcut connection setup, and active shortcut connections. Based on the relative utilization order among the three resources, a learning algorithm is designed to adjust the probability of taking different actions, i.e., adjusting two control parameters in different directions. Simulation results have shown some advantages of this adaptive approach over the static one. However, due to its increased complexity, the practicality of the proposed adaptive scheme remains an open issue.
Moreover, none of the existing schemes or proposals addresses shortcut setup for QoS flows. Since each QoS flow requires certain level of service assurance, a shortcut that provides adequate service for each QoS flow through, for example, a router is required. As stated earlier, the traffic received by a router is generally quite dynamic and its characteristics are unknown in most cases. Thus a robust dynamic scheme for setting up and tearing down shortcuts, that can adjust itself to data traffic dynamics without being unnecessarily complex, is also required.
The present invention is directed to a State Dependent Dynamic Triggering Scheme (SDDTS) that addresses the above mentioned problems of the prior art. In particular the present invention illustrates a practical shortcut triggering scheme for QoS flows. The present invention illustrates a system and method for maximizing the percentage of QoS traffic switched through shortcuts given certain resource limitations, i.e., maximum shortcut setup rate and maximum number of simultaneous shortcut connections. Unlike prior art approaches, the present invention discloses a relatively uncomplicated and practical method based on arithmetic calculations to dynamically adjust two parameters, for example, onset trigger and abatement period. In embodiments of the present invention, the two parameters may be adjusted according to average shortcut setup rate and average number of simultaneous shortcut connections. Thus the present invention is fundamentally different from the xe2x80x9cAdaptive Resource Management for Flow-Based IP/ATM Hybrid Switching Systems,xe2x80x9d approach, discussed earlier, that involves a more complex and unpractical optimization algorithm for probability estimation of actions where the objective is load balancing among three limited resources.
The present invention discloses a practical and robust dynamic scheme for efficiently creating and tearing down shortcuts for QoS data flows through, for example, a data router. One key aspect of such a scheme is to decide, for example, when to setup a shortcut and when to tear down a shortcut, which in turn is governed, for example, by the onset trigger and abatement period trigger values. The dynamic scheme, as disclosed in one embodiment of the present invention, updates those trigger values in an on-line manner so as to achieve a higher and consistent switching efficiency.
One object of the present invention, is to achieve near-optimal switching efficiency in terms of the percentage of bytes and packets that are routed over shortcuts. Because there is a direct relationship between number of shortcuts and the performance target, the more shortcuts, the better performance if there is no physical limit in terms of shortcuts. However, the number of shortcuts a router can support simultaneously does have its physical limits. In addition, a router may also have a limited set up rate, i.e. how fast a shortcut may be set up by the router.
Generally, when the number of simultaneous shortcuts hits its physical limit, a request for setting up a new shortcut must be queued and waits for some existing shortcuts to be torn down. Even though some existing shortcuts may not have any future traffic, they may still stay active until the end of the abatement period. While setup requests wait in the queue, the packets may be sent over the default route, reducing, for example, router efficiency. To avoid applying abatement criterion to the flows with requests queued, the unsatisfied requests are removed from the request queue at the end of each onset period. The flows may be subject to the onset trigger again. Thus there exists a natural bias towards flows with existing shortcuts over flows with unsatisfied requests, even where the existing shortcuts remain idle. Hence, the fewer the number of shortcut setup requests granted, the less the percentage of QoS traffic that is routed through shortcuts. Thus another objective of the present invention is to keep the average shortcut number close to its limit and at the same time to reduce the chances that shortcut number reaches its limit. Embodiments of the present invention, describe an upper threshold and a lower threshold level of the number of shortcuts, and denote the region between the two as the desired stable region. As a result, there is a better chance for future long-lived flows being routed through shortcuts. Thus, it is an object of the present invention to achieve a higher switching efficiency. Since a higher setup rate results in more shortcuts, the same design philosophy applies to the setup rate.
Thus, embodiments of the present invention disclose a dynamic scheme to adjust a plurality of control parameters to set-up and tear down shortcuts for most efficient routing of QoS flows in a network.